﻿#include"UnionFind.hpp"
#include"Graph.hpp"
#include"iostream"

using namespace std;

//void TestGraph()
//{
//	vector<char> tmp = { '0','1','2','3' };
//	Graph<char, int,INT_MAX, true> g(tmp);
//	g.AddEdge('0', '1', 1);
//	g.AddEdge('0', '3', 4);
//	g.AddEdge('1', '3', 2);
//	g.AddEdge('1', '2', 9);
//	g.AddEdge('2', '3', 8);
//	g.AddEdge('2', '1', 5);
//	g.AddEdge('2', '0', 3);
//	g.AddEdge('3', '2', 6);
//	//g.Print();
//}

//void TestGraphMinTree()
//{
//	vector<char> ins = { 'a','b','c','d','e','f','i','g','h' };
//	Graph<char, int> g(ins);
//	g.AddEdge('a', 'b', 4);
//	g.AddEdge('a', 'h', 8);
//	//g.AddEdge('a', 'h', 9);
//	g.AddEdge('b', 'c', 8);
//	g.AddEdge('b', 'h', 11);
//	g.AddEdge('c', 'i', 2);
//	g.AddEdge('c', 'f', 4);
//	g.AddEdge('c', 'd', 7);
//	g.AddEdge('d', 'f', 14);
//	g.AddEdge('d', 'e', 9);
//	g.AddEdge('e', 'f', 10);
//	g.AddEdge('f', 'g', 2);
//	g.AddEdge('g', 'h', 1);
//	g.AddEdge('g', 'i', 6);
//	g.AddEdge('h', 'i', 7);
//	Graph<char, int> kminTree;
//	cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
//	kminTree.Print();
//	Graph<char, int> pminTree;
//	cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
//	pminTree.Print();
//}

void TestGraphDijkstra()
{
	vector<char> tmp = { 's','y','z','t','x' };
	Graph<char, int, INT_MAX, true> g(tmp);
	g.AddEdge('s', 't', 10);
	g.AddEdge('s', 'y', 5);
	g.AddEdge('y', 't', 3);
	g.AddEdge('y', 'x', 9);
	g.AddEdge('y', 'z', 2);
	g.AddEdge('z', 's', 7);
	g.AddEdge('z', 'x', 6);
	g.AddEdge('t', 'y', 2);
	g.AddEdge('t', 'x', 1);
	g.AddEdge('x', 'z', 4);
	vector<int> dist;
	vector<int> parentPath;
	g.Dijkstra('s', dist, parentPath);
	g.PrinrtShotPath('s', dist, parentPath);
}
int main()
{
	TestGraphDijkstra();
	while (1);
}